{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Partitioning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code>，请你将<em> </em><code>s</code><em> </em>分割成一些子串，使每个子串都是 <strong>回文串</strong> 。返回 <code>s</code> 所有可能的分割方案。</p>\n",
    "\n",
    "<p><strong>回文串</strong> 是正着读和反着读都一样的字符串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aab\"\n",
    "<strong>输出：</strong>[[\"a\",\"a\",\"b\"],[\"aa\",\"b\"]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a\"\n",
    "<strong>输出：</strong>[[\"a\"]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 16</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-partitioning](https://leetcode.cn/problems/palindrome-partitioning/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-partitioning](https://leetcode.cn/problems/palindrome-partitioning/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aab\"', '\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        nSubs: int = 1\n",
    "        seen: Set[str] = set()\n",
    "\n",
    "        for c in s:\n",
    "            if c not in seen:\n",
    "                seen.add(c)\n",
    "            else:\n",
    "                nSubs += 1\n",
    "                seen = set([c])\n",
    "\n",
    "        return nSubs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res=1\n",
    "        cnt=0\n",
    "        for c in s:\n",
    "            if cnt&1<<(ord(c)-ord('a')):\n",
    "                cnt=1<<(ord(c)-ord('a'))\n",
    "                res +=1\n",
    "            else:\n",
    "                cnt |=1<<(ord(c)-ord('a'))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count = 1\n",
    "        tmp = \"\"\n",
    "        for i in s:\n",
    "            if i in tmp:\n",
    "                count += 1\n",
    "                tmp = i\n",
    "                continue\n",
    "            tmp = tmp + i\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        mp = Counter()\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if len(mp) == 0:\n",
    "                ans += 1\n",
    "                mp[c] = 1\n",
    "                continue\n",
    "            if c in mp:\n",
    "                ans += 1\n",
    "                mp.clear()\n",
    "            mp[c] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ha=[]\n",
    "        count=0\n",
    "        for ch in s:\n",
    "            if ch in ha:\n",
    "                count+=1\n",
    "                ha=[ch]\n",
    "            else:\n",
    "                ha.append(ch)\n",
    "        return count+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res=1\n",
    "        cnt=set()\n",
    "        for c in s:\n",
    "            if c not in cnt:\n",
    "                cnt.add(c)\n",
    "            else:\n",
    "                cnt=set()\n",
    "                cnt.add(c)\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        j, cnt, window = 0, 0, []\n",
    "        while j < len(s):\n",
    "            if s[j] in window: \n",
    "                cnt += 1\n",
    "                window = []  \n",
    "            window.append(s[j])\n",
    "            j += 1\n",
    "        return cnt + 1  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        r=0\n",
    "        t=set()\n",
    "        res=0\n",
    "        while r<len(s):\n",
    "            if s[r] not in t:\n",
    "                t.add(s[r])\n",
    "            else:\n",
    "                res+=1\n",
    "                t.clear()\n",
    "                t.add(s[r])\n",
    "            r+=1\n",
    "        return res+1\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res=1\n",
    "        cnt=''\n",
    "        for c in s:\n",
    "            if c not in cnt:\n",
    "                cnt +=c\n",
    "            else:\n",
    "                cnt=c\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 使用集合进行辅助\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        total_num = 0\n",
    "        while i < n:\n",
    "            se = set(s[i])\n",
    "            j = i + 1\n",
    "            while j < n:\n",
    "                if s[j] in se:\n",
    "                    # 此时出现重复的，因此需要更新i\n",
    "                    i = j\n",
    "                    total_num += 1\n",
    "                    break\n",
    "                else:\n",
    "                    se.add(s[j])\n",
    "                    j += 1\n",
    "            # 判断j是否为n\n",
    "            if j == n:\n",
    "                total_num += 1\n",
    "                break\n",
    "        return total_num\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        st = set()\n",
    "        for c in s:\n",
    "            if c not in st:\n",
    "                st.add(c)\n",
    "            else:\n",
    "                ans += 1\n",
    "                st = {c}\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = 1\n",
    "        tmp = ''\n",
    "        for c in s:\n",
    "            if c not in tmp:\n",
    "                tmp += c\n",
    "            else:\n",
    "                tmp = c\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 贪心\n",
    "        ans = 0\n",
    "        m = set()\n",
    "        for c in s:\n",
    "            if c in m:\n",
    "                ans += 1\n",
    "                m.clear()\n",
    "            m.add(c)\n",
    "            \n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        nowset = set()\n",
    "        left = 0\n",
    "        lens = len(s)\n",
    "        for i in range(lens):\n",
    "            if s[i] not in nowset:\n",
    "                nowset.add(s[i])\n",
    "            else:\n",
    "                ans += 1\n",
    "                nowset.clear()\n",
    "                nowset.add(s[i])\n",
    "        # if len(nowset) > 0:\n",
    "        #     ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c in vis:\n",
    "                ans += 1\n",
    "                vis = set([c])\n",
    "            else:\n",
    "                vis.add(c)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans=0\n",
    "        cur=''\n",
    "        for i in s:\n",
    "            if i not in cur:\n",
    "                cur+=i\n",
    "            else:\n",
    "                ans+=1\n",
    "                cur=i\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans=1\n",
    "\n",
    "        c=Counter()\n",
    "        for i in range (0,len(s)):\n",
    "            x=s[i]\n",
    "            c[x]+=1\n",
    "            if c[x]==2:\n",
    "                ans+=1\n",
    "                c=Counter()\n",
    "                c[x]=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        appear = set()\n",
    "        ans = 1\n",
    "        for c in s:\n",
    "            if c in appear:\n",
    "                appear.clear()\n",
    "                ans += 1\n",
    "            appear.add(c)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count = 0\n",
    "        d = set()\n",
    "        for i in s:\n",
    "            if i not in d:\n",
    "                d.add(i)\n",
    "            else:\n",
    "                count += 1\n",
    "                d.clear()\n",
    "                d.add(i)\n",
    "        return count + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count=0\n",
    "        a=[]\n",
    "        for i in s:\n",
    "            if i in a :\n",
    "                a=[]\n",
    "                count+=1\n",
    "            a.append(i)\n",
    "        return count+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ret = 0\n",
    "        s1 = ''\n",
    "        for value in s:\n",
    "            if value in s1:\n",
    "                ret = ret + 1\n",
    "                s1 = ''\n",
    "            s1 += value\n",
    "\n",
    "        return ret + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        start,ans = 0,0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] in s[start:i]:\n",
    "                ans += 1\n",
    "                start = i\n",
    "        return ans+1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        set_char = set()\n",
    "        num_substr = 1\n",
    "        for char in s:\n",
    "            if char in set_char:\n",
    "                set_char = set(char)\n",
    "                num_substr += 1\n",
    "            else:\n",
    "                set_char.add(char)\n",
    "        return num_substr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        current_chars = set()  # 用于跟踪当前子字符串中的字符\n",
    "        count = 0  # 子字符串的数量\n",
    "\n",
    "        for char in s:\n",
    "            if char in current_chars:\n",
    "                count += 1\n",
    "                current_chars.clear()\n",
    "            current_chars.add(char)\n",
    "\n",
    "        if current_chars:  # 如果还有剩余的字符，需要为其增加一个子字符串\n",
    "            count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = 1\n",
    "        hashtable = set()\n",
    "        hashtable.add(s[0])\n",
    "        for char in s[1:]:\n",
    "            if char not in hashtable:\n",
    "                hashtable.add(char)\n",
    "            else:\n",
    "                hashtable =set()\n",
    "                hashtable.add(char)\n",
    "                res +=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        current_chars = set()  # 用于跟踪当前子字符串中的字符\n",
    "        count = 0  # 子字符串的数量\n",
    "\n",
    "        for char in s:\n",
    "            if char in current_chars:\n",
    "                count += 1\n",
    "                current_chars.clear()\n",
    "            current_chars.add(char)\n",
    "\n",
    "        if current_chars:  # 如果还有剩余的字符，需要为其增加一个子字符串\n",
    "            count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        left=0\n",
    "        ans=0\n",
    "        letterMapping={}\n",
    "        for i,c in enumerate(s):\n",
    "            if c in letterMapping:\n",
    "                if left<=letterMapping[c]:\n",
    "                    ans+=1\n",
    "                    left=i\n",
    "            letterMapping[c]=i\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        vis = \"\"\n",
    "        for ch in s:\n",
    "            if ch in vis:\n",
    "                vis = \"\"\n",
    "                ans += 1\n",
    "            vis += ch\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        # dic = set()\n",
    "        # ans = 0\n",
    "        # for ch in s:\n",
    "        #     if ch in dic:\n",
    "        #         ans += 1\n",
    "        #         dic = set(ch)\n",
    "        #     else:\n",
    "        #         dic.add(ch)\n",
    "        # return ans + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cur = ''\n",
    "        res = 1\n",
    "        for i in s:\n",
    "            if i in cur:\n",
    "                res += 1\n",
    "                cur = i\n",
    "            else:\n",
    "                cur += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        vis = set()\n",
    "        for i, c in enumerate(s):\n",
    "            if c in vis:\n",
    "                vis.clear()\n",
    "                ans += 1\n",
    "            vis.add(c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 经典的滑动窗口\n",
    "        j, cnt, window = 0, 0, set()\n",
    "        while j < len(s):\n",
    "            if s[j] in window:  # 出现重复值\n",
    "                cnt += 1\n",
    "                window = set()  # 清空窗口\n",
    "            window.add(s[j])\n",
    "            j += 1\n",
    "        return cnt + 1  # 加上最后的一个区间\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        temp = set()\n",
    "        for i in s:\n",
    "            if i not in temp:\n",
    "                temp.add(i)\n",
    "            else:\n",
    "                ans += 1\n",
    "                temp = set(i)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        dic={}\n",
    "        result=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dic:\n",
    "                dic[s[i]]=1\n",
    "            else:\n",
    "                result+=1\n",
    "                dic={s[i]:1}\n",
    "        \n",
    "        return result+1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        集合 = set()\n",
    "        最少次数 = 1\n",
    "        for i in s:\n",
    "            if i in 集合:\n",
    "                最少次数 += 1\n",
    "                集合.clear()\n",
    "            集合.add(i)\n",
    "        return 最少次数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        j, cnt, window = 0, 0, {}\n",
    "        while j < len(s):\n",
    "            if s[j] in window: \n",
    "                cnt += 1\n",
    "                window = {}  \n",
    "            window[s[j]]=0\n",
    "            j += 1\n",
    "        return cnt + 1  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<n:\n",
    "            t=set()\n",
    "            while i<n and s[i] not in t:\n",
    "                t.add(s[i])\n",
    "                i+=1\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = 0\n",
    "        visit = set()\n",
    "        for c in s:\n",
    "            if c in visit:\n",
    "                res += 1\n",
    "                visit = set()\n",
    "            visit.add(c)\n",
    "        return res if visit == set() else res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        visited = set()\n",
    "        for ch in s:\n",
    "            if ch in visited:\n",
    "                ans += 1\n",
    "                visited = set()\n",
    "            visited.add(ch)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        start,ans = 0,0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] in s[start:i]:\n",
    "                ans += 1\n",
    "                start = i\n",
    "        return ans+1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cnt = 1\n",
    "        str_set = set()\n",
    "        for char in s:\n",
    "            if char in str_set:\n",
    "                cnt += 1\n",
    "                str_set.clear()\n",
    "            str_set.add(char)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        index = 0\n",
    "        cur = []\n",
    "        result = 0\n",
    "        while index < len(s):\n",
    "            if s[index] not in cur:\n",
    "                cur.append(s[index])\n",
    "            else:\n",
    "                result += 1\n",
    "                cur = []\n",
    "                continue\n",
    "            index += 1\n",
    "        if cur:\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        集合 = set()\n",
    "        最少次数 = 1\n",
    "        for i in s:\n",
    "            if i in 集合:\n",
    "                最少次数 += 1\n",
    "                集合.clear()\n",
    "            集合.add(i)\n",
    "        return 最少次数\n",
    "        \"\"\"\n",
    "        #位运算\n",
    "        集合 = 0\n",
    "        最少次数 = 1\n",
    "        for i in s:\n",
    "            i  = ord(i)-97\n",
    "            if 集合 >> i & 1:\n",
    "                最少次数 += 1\n",
    "                集合 = 0\n",
    "            集合 |= 1<<i\n",
    "        return 最少次数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        temp = [0] * 26\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            num = ord(s[i]) - ord(\"a\")\n",
    "            if temp[num] == 0:\n",
    "                temp[num] += 1\n",
    "            else:\n",
    "                del(temp)\n",
    "                res += 1\n",
    "                temp = [0] * 26\n",
    "                temp[num] = 1\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        '''\n",
    "        use set: \n",
    "        1. let res is result we want, temp = set()\n",
    "        2. iterate s:\n",
    "            (1)if charcter in set, then res + 1, and set temp to empty\n",
    "            (2) add charcter to set\n",
    "        3. return res +1\n",
    "\n",
    "        O(len(s))\n",
    "\n",
    "        '''\n",
    "\n",
    "        res = 0\n",
    "        temp = set()\n",
    "\n",
    "        for char in s:\n",
    "            if char in temp:\n",
    "                temp = set()\n",
    "                res += 1\n",
    "            temp.add(char)\n",
    "        \n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cont=0\n",
    "        n=len(s)\n",
    "        dp=[]\n",
    "        for i in range(n):\n",
    "            if s[i] in dp:\n",
    "                dp.clear()\n",
    "                cont+=1\n",
    "            dp.append(s[i])\n",
    "        return cont+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        cur = []\n",
    "        res = 1\n",
    "        for i, c in enumerate(s):\n",
    "            if c in set(cur):\n",
    "                res += 1\n",
    "                print(cur)\n",
    "                cur = []\n",
    "            cur.append(c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res, mark = 1, set()\n",
    "        for c in s:\n",
    "            if c in mark:\n",
    "                res += 1\n",
    "                mark.clear()\n",
    "            mark.add(c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        # 经典的滑动窗口\n",
    "        j, cnt, window = 0, 0, set()\n",
    "        while j < len(s):\n",
    "            if s[j] in window:  # 出现重复值\n",
    "                cnt += 1\n",
    "                window = set()  # 清空窗口\n",
    "            window.add(s[j])\n",
    "            j += 1\n",
    "        return cnt + 1  # 加上最后的一个区间\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans, t = 0, set()\n",
    "        for ch in s:\n",
    "            if ch not in t:\n",
    "                t.add(ch)\n",
    "            else:\n",
    "                ans += 1\n",
    "                t = set([ch])\n",
    "        if t:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        '''\n",
    "        use set: \n",
    "        1. let res is result we want, temp = set()\n",
    "        2. iterate s:\n",
    "            (1)if charcter in set, then res + 1, and set temp to empty\n",
    "            (2) if not, add charcter to set\n",
    "        3. return result\n",
    "\n",
    "        O(len(s))\n",
    "\n",
    "        '''\n",
    "\n",
    "        res = 0\n",
    "        temp = set()\n",
    "\n",
    "        for char in s:\n",
    "            if char in temp:\n",
    "                temp = set()\n",
    "                res += 1\n",
    "            temp.add(char)\n",
    "        \n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        d = defaultdict(int)\n",
    "        cnt = 1\n",
    "        left = 0\n",
    "        while left < len(s):\n",
    "            if d[s[left]] == 1:\n",
    "                d = defaultdict(int)\n",
    "                cnt += 1\n",
    "            d[s[left]] += 1\n",
    "            left += 1\n",
    "        return cnt                                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        record = {}\n",
    "        count = 1\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            if c not in record:\n",
    "                record[c]=1\n",
    "            else:\n",
    "                record = {}\n",
    "                record[c] = 1\n",
    "                count+=1\n",
    "\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        mask, res = 0, 1\n",
    "        ordA = ord('a')\n",
    "        for c in s:\n",
    "            m = 1<<(ord(c) - ordA)\n",
    "            if mask & m:\n",
    "                mask = 0\n",
    "                res += 1\n",
    "            mask |= m\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        res = 0\n",
    "        hashset = set()\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            hashset.add(s[i])\n",
    "            res += 1\n",
    "            \n",
    "            j = i + 1\n",
    "            while j < n and s[j] not in hashset:\n",
    "                hashset.add(s[j])\n",
    "                j += 1\n",
    "                \n",
    "            i = j\n",
    "            hashset.clear()\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        count=1\n",
    "        temp=\"\"\n",
    "        for i in s:\n",
    "            if i not in temp:\n",
    "                temp+=i\n",
    "            else:\n",
    "                count+=1\n",
    "                temp=i\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        tmp_s = \"\"\n",
    "        cn = 0\n",
    "        for ss in s:\n",
    "            print(ss, tmp_s)\n",
    "            if ss not in tmp_s:\n",
    "                tmp_s = tmp_s + ss\n",
    "            else:\n",
    "                tmp_s = ss\n",
    "                cn += 1\n",
    "        if tmp_s != \"\":\n",
    "            return cn + 1\n",
    "        else:\n",
    "            return cn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "\n",
    "        sub_s = set()\n",
    "\n",
    "        cnt = 1\n",
    "        for char in s:\n",
    "            if char not in sub_s:\n",
    "                sub_s.add(char)\n",
    "                print(sub_s, cnt)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                sub_s = set()\n",
    "                sub_s.add(char)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        my_dict = {}\n",
    "        count = 0\n",
    "        start = 0\n",
    "        for index, char in enumerate(s):\n",
    "            if char not in my_dict:\n",
    "                my_dict[char] = index\n",
    "            elif start > my_dict[char]:\n",
    "                my_dict[char] = index\n",
    "            else:\n",
    "                \n",
    "                count += 1\n",
    "                start = index\n",
    "                my_dict[char] = index\n",
    "                print(start)\n",
    "        if start <= len(s) - 1:\n",
    "            # results.append(s[start:])\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        start,ans = 0,0\n",
    "        arr = list(s)\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i] in arr[start:i]:\n",
    "                ans += 1\n",
    "                start = i\n",
    "                # print(i)\n",
    "        return ans+1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        base = 0\n",
    "        ans = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] in s[base:i]:\n",
    "                ans += 1\n",
    "                base = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        res = []\n",
    "        tmp = \"\"\n",
    "        for i in s:\n",
    "            if i not in tmp:\n",
    "                tmp+=i\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp=i\n",
    "        res.append(tmp)\n",
    "        return(len(res))\n",
    "#        return(max(s.count(x) for x in s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        lst = ['']\n",
    "        l = len(s)\n",
    "        cnt = 0\n",
    "        for i in range(l):\n",
    "            if s[i] not in lst[cnt]:\n",
    "                lst[cnt] += s[i]\n",
    "            else:\n",
    "                cnt +=1\n",
    "                lst.append(s[i])\n",
    "        return len(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionString(self, s: str) -> int:\n",
    "        lst = ['']\n",
    "        l = len(s)\n",
    "        cnt = 0\n",
    "        for i in range(l):\n",
    "            if s[i] not in lst[cnt]:\n",
    "                lst[cnt] += s[i]\n",
    "            else:\n",
    "                cnt +=1\n",
    "                lst.append(s[i])\n",
    "        return len(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:\n",
    "        # 排除一些特殊情况\n",
    "        if m < target:\n",
    "            return -1\n",
    "        elif m == 1 and target == 1:\n",
    "            if houses[0] != 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return cost[0][0]\n",
    "\n",
    "        # 3维的动态规划\n",
    "        INF = 10 ** 9\n",
    "\n",
    "        # 初始化dp数组\n",
    "        dp = [[[INF for _ in range(target + 1)] for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        # 对某些数值进一步初始化,即 房屋编号为0且分区为0的dp——初始化易导致出错\n",
    "        for j in range(n + 1):\n",
    "            dp[0][j][0] = 0\n",
    "\n",
    "        # 开始dp\n",
    "        # 首先遍历房子序号\n",
    "        for i in range(m + 1):\n",
    "            color = houses[i - 1]\n",
    "            # 接着遍历决策颜色与分区\n",
    "            for j in range(1, n + 1):\n",
    "                partitionEnd = min(i + 1, target + 1)\n",
    "                for k in range(1, partitionEnd):\n",
    "                    # 如果可以涂色,从不新增分区与新增分区中找到min值,再加上cost\n",
    "                    if color == 0:\n",
    "                        # 1、不新增分区\n",
    "                        tmp1 = dp[i - 1][j][k]\n",
    "                        \n",
    "                        #2、新增分区\n",
    "                        tmp2 = INF\n",
    "                        for p in range(1, n + 1):\n",
    "                            # 这个地方易错,等式右侧是j而不是color！！！！\n",
    "                            if p != j:\n",
    "                                tmp2 = min(tmp2, dp[i - 1][p][k - 1])\n",
    "                        \n",
    "                        # 当前取值即为\n",
    "                        dp[i][j][k] = min(tmp1, tmp2) + cost[i - 1][j - 1]\n",
    "                        \n",
    "                    # 如果不可以涂色\n",
    "                    else:\n",
    "                        # 如果决策的颜色不同于当前颜色\n",
    "                        if j != color:\n",
    "                            dp[i][j][k] = INF\n",
    "                        else:\n",
    "                            # 1、不新增分区\n",
    "                            tmp1 = dp[i - 1][j][k]\n",
    "                            \n",
    "                            #2、新增分区\n",
    "                            tmp2 = INF\n",
    "                            for p in range(1, n + 1):\n",
    "                            # 这个地方易错,等式右侧是j而不是color！！！！\n",
    "                                if p != j:\n",
    "                                    tmp2 = min(tmp2, dp[i - 1][p][k - 1])\n",
    "                            \n",
    "                            # 当前取值即为\n",
    "                            dp[i][j][k] = min(tmp1, tmp2)\n",
    "        # print(dp)\n",
    "\n",
    "        # 得到结果\n",
    "        ans = INF\n",
    "        for j in range(1, n + 1):\n",
    "            ans = min(ans, dp[m][j][target])\n",
    "        if ans != INF:\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        # import functools\n",
    "        n=len(s)\n",
    "        # dp\n",
    "        # dp[i] define as partition when i==rightmost\n",
    "        # loop last subarray from i <--to left, \n",
    "        # when lastsub is palindrome, refer to dp[i-len(sub)]+1\n",
    "        dp=[float('inf') for i in range(n)]\n",
    "        dp[0]=0#one letter is palindrome, no need cut\n",
    "        # @functools.lru_cache(maxsize=None)\n",
    "        # def is_palindrome(left,right):#check subarray of s\n",
    "        #     if left>=right:return True\n",
    "        #     if s[left]!=s[right]:return False\n",
    "        #     return is_palindrome(left+1,right-1)\n",
    "\n",
    "        # update: try pre-calculate is_palindrome\n",
    "        is_palindrome=[[None for left in range(n)]for right in range(n)]\n",
    "        for right_left in range(n):#right-left\n",
    "            for left in range(0,n-right_left):\n",
    "                right=left+right_left\n",
    "                if left==right:is_palindrome[left][right]=True;continue\n",
    "                if s[left]!=s[right]:is_palindrome[left][right]=False\n",
    "                elif right-left+1==2:#if len==2\n",
    "                    is_palindrome[left][right]=True\n",
    "                else:#refer to left+1, right-1\n",
    "                    is_palindrome[left][right]=is_palindrome[left+1][right-1]\n",
    "                \n",
    "        for i in range(1,n):\n",
    "            if is_palindrome[0][i]:#if all is palindrome\n",
    "                dp[i]=0;continue\n",
    "            for len_subarray in range(1,i+1):#check each palindrome sub\n",
    "                # subarray=i-len_subarray,i\n",
    "                if is_palindrome[i-len_subarray+1][i]:\n",
    "                    dp[i]=min(dp[i],dp[i-len_subarray]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "        # dp[i][j] denotes the where the subarray s[i: j+1] is Palindrome\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]\n",
    "        \n",
    "        p_dp = [float('inf')] * n \n",
    "        # p_dp[i] denotes the min partition of palindrome substring for s[:i+1]\n",
    "\n",
    "        for i in range(n):\n",
    "            if dp[0][i]:\n",
    "                p_dp[i] = 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if dp[j+1][i]:\n",
    "                    p_dp[i] = min(p_dp[i], p_dp[j] + 1)\n",
    "\n",
    "        return p_dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def count(beg, end):\n",
    "            if beg >= end:\n",
    "                return 0\n",
    "            else:\n",
    "                return (s[beg] != s[end]) + count(beg+1, end-1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def partition(i, k):\n",
    "            if k == 1:\n",
    "                return count(0,i)\n",
    "\n",
    "            return min(partition(j, k-1) + count(j+1, i) for j in range(k-2, i))\n",
    "\n",
    "        return partition(len(s)-1, k)\n",
    "           \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def count(beg, end):\n",
    "            if beg >= end:\n",
    "                return 0\n",
    "            else:\n",
    "                return (s[beg] != s[end]) + count(beg+1, end-1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def partition(i, k):\n",
    "            if k == 1:\n",
    "                return count(0,i)\n",
    "\n",
    "            return min(partition(j, k-1) + count(j+1, i) for j in range(k-2, i))\n",
    "\n",
    "        return partition(len(s)-1, k)\n",
    "           \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Manacher:\n",
    "    def __init__(self, string=''):\n",
    "        self.string = string\n",
    "\n",
    "    def add_char(self):\n",
    "        add_string = '^'\n",
    "        for char in self.string:\n",
    "            add_string += '@' + char\n",
    "        add_string += '@*'\n",
    "        return add_string\n",
    "    \n",
    "    def get_p(self): \n",
    "        self.add_string = self.add_char()\n",
    "        self.P = [0] * len(self.add_string)\n",
    "        R, mid = 0, 0\n",
    "        for i in range(1, len(self.add_string)-1):\n",
    "            self.P[i] = min(self.P[mid*2-i], R-i) if R > i else 0\n",
    "            while self.add_string[i+1+self.P[i]] == self.add_string[i-1-self.P[i]]:\n",
    "                self.P[i] +=1\n",
    "            if i + self.P[i] > R:\n",
    "                R = i + self.P[i]\n",
    "                mid = i\n",
    "        return self.P\n",
    "    \n",
    "    def check_partition_s(self, l, r): # 判断在串S的区间[l,r]的子串是否为回文串。\n",
    "        l, r = l * 2 + 2, r * 2 + 2\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        manacher = Manacher(s)\n",
    "        manacher.get_p()\n",
    "        n = len(s)\n",
    "        pre, suf = [], []\n",
    "        pre_vis = [0] * n \n",
    "        suf_vis = [0] * n\n",
    "        for i in range(0, n):\n",
    "            if manacher.check_partition_s(0, n-1-i):\n",
    "                pre.append(n-i-1)\n",
    "                pre_vis[n-i-1] = 1\n",
    "            if manacher.check_partition_s(i, n-1):\n",
    "                suf.append(i)\n",
    "                suf_vis[i] = 1\n",
    "\n",
    "        suf_n, cnt = len(suf), 0\n",
    "        for i in range(n):\n",
    "            if pre_vis[i]:\n",
    "                while cnt < suf_n and suf[cnt] < i + 2:\n",
    "                    cnt +=1\n",
    "                if cnt < suf_n and manacher.check_partition_s(i+1, suf[cnt]-1):\n",
    "                    return True\n",
    "        \n",
    "        # print(pre, suf, pre_vis, suf_vis)\n",
    "        pre_n, cnt = len(pre), 0\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if suf_vis[i]:\n",
    "                while cnt < pre_n and pre[cnt] + 2 > i:\n",
    "                    cnt +=1\n",
    "                if cnt < pre_n and manacher.check_partition_s(pre[cnt]+1, i-1):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Manacher:\n",
    "    def __init__(self, string=''):\n",
    "        self.string = string\n",
    "\n",
    "    def add_char(self):\n",
    "        \"\"\"\n",
    "        对字符串预处理填充'#'，使得字符串长度强行满足奇数对称。\n",
    "        同时头尾插入一对不匹配字符，添加P数组计算的边界情况。\n",
    "        \"\"\"\n",
    "        add_string = '^'\n",
    "        for char in self.string:\n",
    "            add_string += '@' + char\n",
    "        add_string += '@*'\n",
    "        return add_string\n",
    "    \n",
    "    def get_p(self): # Manacher算法核心，利用对称性中心扩展O(n)计算P数组\n",
    "        self.add_string = self.add_char()\n",
    "        self.P = [0] * len(self.add_string)\n",
    "        R, mid = 0, 0\n",
    "        for i in range(1, len(self.add_string)-1):\n",
    "            self.P[i] = min(self.P[mid*2-i], R-i) if R > i else 0\n",
    "            while self.add_string[i+1+self.P[i]] == self.add_string[i-1-self.P[i]]:\n",
    "                self.P[i] +=1\n",
    "            if i + self.P[i] > R:\n",
    "                R = i + self.P[i]\n",
    "                mid = i    \n",
    "        return self.P\n",
    "    \n",
    "    def max_palindrome(self):\n",
    "        \"\"\"\n",
    "        利用manacher已计算好的P数组，输出最长的回文子串。可以直接解决 Leetcode 5. 最长回文子串\n",
    "        \"\"\"\n",
    "        self.get_p()\n",
    "        max_len, max_index = 0, 0\n",
    "        for index, value in enumerate(self.P):\n",
    "            if value > max_len:\n",
    "                max_len, max_index = value, index\n",
    "        start_index = (max_index - max_len) // 2\n",
    "        return self.string[start_index: start_index+max_len]\n",
    "\n",
    "    def check_partition_s(self, l, r): # 判断在串S的区间[l,r]的子串是否为回文串。\n",
    "        l, r = l * 2 + 2, r * 2 + 2\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "        \n",
    "    def check_partition_p(self, l, r): # 判断在数组P的区间[l,r]内是否为回文串。\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        manacher = Manacher(s)\n",
    "        manacher.get_p()\n",
    "        n = len(s)\n",
    "        pre, suf = [], []\n",
    "        pre_vis, suf_vis = [0] * n, [0] * n\n",
    "        for i in range(0, n):\n",
    "            if manacher.check_partition_s(0, n-1-i):\n",
    "                pre.append(n-i-1)\n",
    "                pre_vis[n-i-1] = 1\n",
    "            if manacher.check_partition_s(i, n-1):\n",
    "                suf.append(i)\n",
    "                suf_vis[i] = 1\n",
    "\n",
    "        suf_n, cnt = len(suf), 0\n",
    "        for i in range(n):\n",
    "            if pre_vis[i]:\n",
    "                while cnt < suf_n and suf[cnt] < i + 2:\n",
    "                    cnt +=1\n",
    "                if cnt < suf_n and manacher.check_partition_s(i+1, suf[cnt]-1):\n",
    "                    return True\n",
    "        pre_n, cnt = len(pre), 0\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if suf_vis[i]:\n",
    "                while cnt < pre_n and pre[cnt] + 2 > i:\n",
    "                    cnt +=1\n",
    "                if cnt < pre_n and manacher.check_partition_s(pre[cnt]+1, i-1):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        def isPalindrome(i, j):\n",
    "            while i < j: \n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        @cache\n",
    "        def recur(i):\n",
    "            if i == n:\n",
    "                return [[]] \n",
    "            ans = []\n",
    "            for j in range(i, n):\n",
    "                if isPalindrome(i, j):\n",
    "                    ans += [[s[i:j+1]] + x for x in recur(j + 1)]\n",
    "            return ans\n",
    "        return recur(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return []\n",
    "        res = []\n",
    "        dp = []\n",
    "        for _ in range(len(s)):\n",
    "            dp.append([False] * len(s))\n",
    "        self.helper(s, 0, res, [], dp)\n",
    "        return res\n",
    "\n",
    "    def helper(self, s, cur, res, temp, dp):\n",
    "        if cur == len(s):\n",
    "            res.append(copy.deepcopy(temp))\n",
    "            return\n",
    "        for i in range(cur, len(s)):\n",
    "            if self.is_plaindrome(cur, i, dp, s):\n",
    "                dp[cur][i] = True\n",
    "                temp.append(s[cur:i + 1])\n",
    "                self.helper(s, i + 1, res, temp, dp)\n",
    "                temp.pop()\n",
    "\n",
    "    def is_plaindrome(self, i, j, dp, s):\n",
    "        if s[i] == s[j]:\n",
    "            if i == j or j == i + 1 or dp[i + 1][j - 1]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if not s:\n",
    "            return []\n",
    "        temp = []\n",
    "        res = []\n",
    "        self.DFS(s, temp, res)\n",
    "        return res\n",
    "        \n",
    "    def DFS(self, s, temp, res):\n",
    "        if not s:\n",
    "            res.append(copy.copy(temp))\n",
    "        for length in range(1, len(s)+1):\n",
    "            if(self.isPalindrome(s[:length])):\n",
    "                temp.append(s[:length])\n",
    "                self.DFS(s[length:], temp, res)\n",
    "                temp.pop()\n",
    "    \n",
    "    def isPalindrome(self, s: str) -> bool:\n",
    "        if not s:\n",
    "            return True\n",
    "        temp = ''\n",
    "        s = s.lower()\n",
    "        for c in s:\n",
    "            if c.isalnum():\n",
    "                temp += c\n",
    "        l = len(temp)\n",
    "        if not temp:\n",
    "            return True\n",
    "        \n",
    "        for i in range(0, l):\n",
    "            if temp[i] != temp[l-1-i]:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ispar(self,s):\n",
    "        l=len(s)\n",
    "        for i in range(l//2):\n",
    "            if s[i]!=s[l-1-i]:\n",
    "                return 0\n",
    "        return 1\n",
    "    \n",
    "    def func(self,res,tmp,start,n,s):\n",
    "        if start>=n:\n",
    "            res.append(tmp[:])\n",
    "            return\n",
    "        for i in range(start,n):\n",
    "            if self.ispar(s[start:i+1])==1:\n",
    "                tmp.append(s[start:i+1])\n",
    "                self.func(res,tmp,i+1,n,s)\n",
    "                del tmp[-1]\n",
    "        return\n",
    "    \n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        l=len(s)\n",
    "        res=[]\n",
    "        self.func(res,[],0,l,s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        if len(s) == 0:\n",
    "            return []\n",
    "        par_list = [[] for col in range(len(s))]\n",
    "        return self.find_pal_par_list(s, len(s) - 1, par_list)\n",
    "\n",
    "    def find_pal_par_list(self, s, endIndex, par_list):\n",
    "        if endIndex == -1:\n",
    "            return [[]]\n",
    "        if len(par_list[endIndex]) != 0:\n",
    "            return par_list[endIndex]\n",
    "        i = 0\n",
    "        while endIndex - i >= 0:\n",
    "            if self.isPalindrome(s, endIndex - i, endIndex):\n",
    "                last = self.find_pal_par_list(s, endIndex - i - 1, par_list)\n",
    "                pal = s[endIndex - i: endIndex + 1]\n",
    "                for each_par in last:\n",
    "                    par_list[endIndex].insert(0, each_par + [pal])\n",
    "            i += 1\n",
    "        return par_list[endIndex]\n",
    "\n",
    "    def isPalindrome(self, s, i, j):\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        dp = [[] for _ in range(len(s)+1)]\n",
    "        for i in range(1, len(s)+1):\n",
    "            for j in range(i):\n",
    "                if self.isPalindrome(s[j:i]):\n",
    "                    if len(dp[j]) > 0:\n",
    "                        for l in dp[j]:\n",
    "                            dp[i].append(l+[s[j:i]])\n",
    "                    else:\n",
    "                        dp[i].append([s[j:i]])\n",
    "        \n",
    "        return dp[-1]\n",
    "                        \n",
    "    def isPalindrome(self,s):\n",
    "        for i in range(len(s)>>1):\n",
    "            if s[i] != s[len(s)-1-i]:\n",
    "                return False \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        \n",
    "        length = len(s)\n",
    "        palindrom = []\n",
    "        for i in range(0, length):\n",
    "            row = []\n",
    "            for j in range(0, length):\n",
    "                if i == j:\n",
    "                    row.append(1)\n",
    "                else:\n",
    "                    row.append(0)\n",
    "            palindrom.append(row)\n",
    "            \n",
    "        for j in range(1, length):\n",
    "            for i in range(1, j):\n",
    "                if palindrom[i][j - 1] == 1 and s[i - 1] == s[j]:\n",
    "                    palindrom[i - 1][j] = 1\n",
    "            if s[j - 1] == s[j]:\n",
    "                palindrom[j - 1][j] = 1\n",
    "                    \n",
    "        # for i in range(0, length):\n",
    "        #     for j in range(i, length):\n",
    "        #         if palindrom[i][j] == 1:\n",
    "        #             print(s[i:j+1])\n",
    "        \n",
    "        partitionDict = {}\n",
    "        for i in range(length - 1, -1, -1):\n",
    "            subPartitions = []\n",
    "            for j in range(i, length):\n",
    "                if palindrom[i][j] == 1:\n",
    "                    if j == length - 1:\n",
    "                        subPartitions.append([s[i:j + 1]])\n",
    "                    else:\n",
    "                        for subPartition in partitionDict[str(j + 1) + ',' + str(length - 1)]:\n",
    "                            newSubPartition = subPartition.copy()\n",
    "                            newSubPartition.insert(0, s[i:j + 1])\n",
    "                            subPartitions.append(newSubPartition)\n",
    "            partitionDict[str(i) + ',' + str(length - 1)] = subPartitions\n",
    "            # print(str(i) + ',' + str(length - 1) + \":\")\n",
    "            # print(subPartitions)\n",
    "        \n",
    "        return partitionDict['0,' + str(length - 1)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if not s:\n",
    "            return []\n",
    "        result = []\n",
    "        self.dfs(s, result, [])\n",
    "        return result\n",
    "\n",
    "    def dfs(self, s, result, stringlist):\n",
    "        if len(s) == 0:\n",
    "            result.append(list(stringlist))\n",
    "            return \n",
    "        for i in range(1, len(s) + 1):\n",
    "            if s[:i] == s[:i][::-1]:\n",
    "                self.dfs(s[i:], result, stringlist + [s[:i]])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#回溯\n",
    "#Time:O(n²)\n",
    "#Space:O(n)\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if len(s)==0:\n",
    "            return [[]]\n",
    "        if len(s)==1:\n",
    "            return [[s]]\n",
    "        tmp = []\n",
    "        for i in range(1,len(s)+1):\n",
    "            left = s[:i]\n",
    "            right = s[i:]\n",
    "            if left == left[::-1]:\n",
    "                right = self.partition(right)\n",
    "                for i in range(len(right)):\n",
    "                    tmp.append([left]+right[i])\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def backtrack(s,tmp):\n",
    "            if not s:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                for i in range(1,len(s)+1):\n",
    "                    if s[:i] == s[:i][::-1]:\n",
    "                        backtrack(s[i:],tmp+[s[:i]])\n",
    "            \n",
    "        backtrack(s,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def backtrace(start):\n",
    "            if start == n:\n",
    "                results.append(result[:])\n",
    "            else:\n",
    "                # 此处需要增加一个回文判断的逻辑\n",
    "                # 但是整体框架不用变动\n",
    "                for i in range(start, n):\n",
    "                    substr = s[start:i + 1]\n",
    "                    if substr == substr[::-1]:\n",
    "                        result.append(substr)\n",
    "                        backtrace(i + 1)\n",
    "                        result.pop()\n",
    "        n = len(s)\n",
    "        results = []\n",
    "        result = []\n",
    "\n",
    "        backtrace(0)\n",
    "\n",
    "        return results\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def backtrace(start):\n",
    "            if start == n:\n",
    "                results.append(result[:])\n",
    "            else:\n",
    "                for i in range(start, n):\n",
    "                    substr = s[start:i + 1]\n",
    "                    if substr == substr[::-1]:\n",
    "                        result.append(substr)\n",
    "                        backtrace(i + 1)\n",
    "                        result.pop()\n",
    "\n",
    "        n = len(s)\n",
    "        results = []\n",
    "        result = []\n",
    "\n",
    "        backtrace(0)\n",
    "\n",
    "        return results\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        # ans = []\n",
    "        # def recur_help(s,begin=0,split=[]):\n",
    "        #     if begin == len(s):\n",
    "        #         ans.append(split[:])\n",
    "        #     # else:\n",
    "        #     for i in range(begin+1,len(s)+1):\n",
    "        #         if self.isPalindrome(s[begin:i]):\n",
    "        #             split.append(s[begin:i])\n",
    "        #             recur_help(s,begin=i,split=split)\n",
    "        #             split.pop()\n",
    "        # recur_help(s)\n",
    "        # return ans\n",
    "\n",
    "        # 动态规划\n",
    "        # 若已知s[:1],s[:2],...,s[:len(s)-1]的分割方案，\n",
    "        # 若s[j:len(s)]是回文串，则s[:j]的分割方案加上s[j:len(s)]成为s的一种分割方案\n",
    "        ans = [[[s[0]]]]\n",
    "        for i in range(2,len(s)+1):\n",
    "            ans.append([])\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if self.isPalindrome(s[j:i]):\n",
    "                    if j - 1 >= 0:\n",
    "                        for p in ans[j-1]:\n",
    "                            ans[i-1].append(p+[s[j:i]])\n",
    "                    else:\n",
    "                        ans[i-1].append([s[j:i]])\n",
    "        return ans[-1]\n",
    "    def isPalindrome(self,s):\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def isPa(s):\n",
    "            if s == \"\":\n",
    "                return True\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(s-1)\n",
    "                while l<=r:\n",
    "                    if s[l] != s[r]:\n",
    "                        return False\n",
    "                return True\n",
    "        \n",
    "        is_pa = [[False] * (len(s)+1) for _ in range(len(s))]\n",
    "\n",
    "        for i in range(1,len(s)+1):\n",
    "            for start in range(0, len(s)-i+1):\n",
    "                end = start + i\n",
    "                if i == 1:\n",
    "                    is_pa[start][end] = True\n",
    "                elif i == 2:\n",
    "                    is_pa[start][end] = s[start] == s[start+1]\n",
    "                else:\n",
    "                    is_pa[start][end] = is_pa[start+1][end-1] and s[start] == s[end-1]\n",
    "        \n",
    "        res = [[[]]]\n",
    "        for i in range(1, len(s)+1):\n",
    "            cur = []\n",
    "            for j in range(0, i):\n",
    "                #print(j)\n",
    "                #print(i, is_pa[j][i])\n",
    "                if is_pa[j][i]:\n",
    "                    #print(res[j])\n",
    "                    for item in res[j]:\n",
    "                        cur.append(item + [s[j:i]])\n",
    "            res.append(cur)\n",
    "        \n",
    "        return(res[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        dp = [[] for _ in range(len(s) + 1)]\n",
    "        dp[-1] = [[]]\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            for j in range(i + 1, len(s) + 1):\n",
    "                if s[i:j] == s[i:j][::-1]:\n",
    "                    for each in dp[j]:\n",
    "                        dp[i].append([s[i:j]] + each)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.hw_map = dict()\n",
    "        self.seq_map = dict()\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        \"\"\"\n",
    "        F(s, begin, end) = Huiwen(s, begin, begin + 1) * F(s, begin + 1, end) \n",
    "                         + Huiwen(s, begin, begin + 2) * F(s, begin + 1, end) \n",
    "                         ...\n",
    "                         + Huiwen(s, begin, begin) * 1 \n",
    "        \"\"\"\n",
    "        str_a = [x for x in s]\n",
    "        result = self.dfs_huiwen(s, 0, len(s))\n",
    "        return result\n",
    "\n",
    "    def dfs_huiwen(self, s, begin, end):\n",
    "        str_seq = s[begin: end]\n",
    "        if str_seq in self.seq_map:\n",
    "            return self.seq_map[str_seq]\n",
    "        t = end - begin\n",
    "        if t <= 0:\n",
    "            return [[]]\n",
    "        if t == 1:\n",
    "            return [[s[begin]]]\n",
    "        r = []\n",
    "        for i in  range(begin + 1 , end + 1):\n",
    "            first_s = s[begin: i]\n",
    "            if self.is_huiwen_str(first_s):\n",
    "                lr = self.dfs_huiwen(s, i, end)\n",
    "                if i >= end or lr:\n",
    "                    nr = []\n",
    "                    for sub in lr:\n",
    "                        nr.append([first_s] + sub)\n",
    "                    r.extend(nr)\n",
    "        self.seq_map[str_seq] = r\n",
    "        return r\n",
    "\n",
    "    def is_huiwen_str(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return False\n",
    "        if n == 1:\n",
    "            return True\n",
    "        if s in self.hw_map:\n",
    "            return self.hw_map[s]\n",
    "        r = True\n",
    "        half = (int)(n / 2)\n",
    "        for i in range(half):\n",
    "            if s[i] != s[n - i - 1]:\n",
    "                r = False\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPalindrome(s: str) -> bool:\n",
    "    if len(s) <= 1:\n",
    "        return True\n",
    "    first = 0\n",
    "    second = len(s) - 1\n",
    "    while first < second:\n",
    "        while not s[first].isalnum() and first < second:\n",
    "            first += 1\n",
    "        while not s[second].isalnum() and first < second:\n",
    "            second -= 1\n",
    "        if s[first].lower() != s[second].lower():\n",
    "            return False\n",
    "        first += 1\n",
    "        second -= 1\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def helper(cur_str, path, result):\n",
    "            if len(cur_str) == 0:\n",
    "                if len(path) != 0:\n",
    "                    result.append(deepcopy(path))\n",
    "                return\n",
    "            for index in range(1, len(cur_str)+1):\n",
    "                prefix = cur_str[:index]\n",
    "                if prefix not in dp:\n",
    "                    dp[prefix] = isPalindrome(prefix)\n",
    "                if not dp[prefix]:\n",
    "                    continue\n",
    "                path.append(prefix)\n",
    "                helper(cur_str[index:], path, result)\n",
    "                path.pop()\n",
    "        if len(s) == 0:\n",
    "            return [[]]\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        dp = dict()\n",
    "        path = []\n",
    "        result = []\n",
    "        helper(s, path, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def x(s):\n",
    "            n = len(s)\n",
    "            for i in range(n // 2):\n",
    "                if s[i] != s[n - 1 - i]:\n",
    "                    return False\n",
    "            return True\n",
    "        @lru_cache(None)\n",
    "        def f(s):\n",
    "            if len(s) == 0:\n",
    "                return []\n",
    "            elif len(s) == 1:\n",
    "                return [[s]]\n",
    "            else:\n",
    "                ans = []\n",
    "                for i in range(1, len(s)):\n",
    "                    if x(s[:i]):\n",
    "                        for k in f(s[i:]):\n",
    "                            ans.append([s[:i]] + k)\n",
    "                if x(s):\n",
    "                    ans.append([s])\n",
    "                return ans\n",
    "        return f(s)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.hw_map = dict()\n",
    "        self.seq_map = dict()\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        \"\"\"\n",
    "        F(s, begin, end) = Huiwen(s, begin, begin + 1) * F(s, begin + 1, end) \n",
    "                         + Huiwen(s, begin, begin + 2) * F(s, begin + 1, end) \n",
    "                         ...\n",
    "                         + Huiwen(s, begin, begin) * 1 \n",
    "        \"\"\"\n",
    "        str_a = [x for x in s]\n",
    "        result = self.dfs_huiwen(s, 0, len(s))\n",
    "        return result\n",
    "\n",
    "    def dfs_huiwen(self, s, begin, end):\n",
    "        if (begin, end) in self.seq_map:\n",
    "            return self.seq_map[(begin, end)]\n",
    "        t = end - begin\n",
    "        if t <= 0:\n",
    "            return [[]]\n",
    "        if t == 1:\n",
    "            return [[s[begin]]]\n",
    "        r = []\n",
    "        for i in  range(begin + 1 , end + 1):\n",
    "            first_s = s[begin: i]\n",
    "            if self.is_huiwen_str(first_s):\n",
    "                lr = self.dfs_huiwen(s, i, end)\n",
    "                if i >= end or lr:\n",
    "                    nr = []\n",
    "                    for sub in lr:\n",
    "                        nr.append([first_s] + sub)\n",
    "                    r.extend(nr)\n",
    "        self.seq_map[(begin,end)] = r\n",
    "        return r\n",
    "\n",
    "    def is_huiwen_str(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return False\n",
    "        if n == 1:\n",
    "            return True\n",
    "        if s in self.hw_map:\n",
    "            return self.hw_map[s]\n",
    "        r = True\n",
    "        half = (int)(n / 2)\n",
    "        for i in range(half):\n",
    "            if s[i] != s[n - i - 1]:\n",
    "                r = False\n",
    "        self.hw_map[s] = r\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        huiwenMemo = {}\n",
    "        def check(i, j): # s[i:j] 是否是回文串\n",
    "            if (i,j) not in huiwenMemo:\n",
    "                if j - i <= 1: \n",
    "                    huiwenMemo[(i,j)] = True\n",
    "                else:\n",
    "                    huiwenMemo[(i,j)] =  check(i+1, j-1) if s[i]==s[j-1] else False\n",
    "            return huiwenMemo[(i,j)]\n",
    "        \n",
    "\n",
    "        n = len(s)\n",
    "        dpMemo = {}\n",
    "        def dp(i): # s[i:] 分割成的回文串\n",
    "            if i not in dpMemo:\n",
    "                res = []\n",
    "                for k in range(i, n): # i=[i,..,n-1]\n",
    "                    if k==i:\n",
    "                        if check(i, n): # k==i时，检查整个字符串是否是回文\n",
    "                            res.append([s[i:]])\n",
    "                    else:\n",
    "                        if check(i, k):\n",
    "                            res.extend([[s[i:k]]+each for each in dp(k)])\n",
    "                dpMemo[i] = res\n",
    "            return dpMemo[i]\n",
    "        \n",
    "        return dp(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        @lru_cache(None)\n",
    "        def check(b, e):\n",
    "            if b == e:\n",
    "                return True\n",
    "            if b + 1 == e:\n",
    "                return s[b] == s[e]\n",
    "            return check(b+1, e-1) and s[b] == s[e]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get(b, e):\n",
    "            if b == e:\n",
    "                return [[s[b]]]\n",
    "            if b > e:\n",
    "                return [[]]\n",
    "            ans = []\n",
    "            for i in range(b, e+1):\n",
    "                if check(b, i):\n",
    "                    for item in get(i+1, e):\n",
    "                        ans.append([s[b:i+1]] + item)\n",
    "            return ans\n",
    "        \n",
    "        if not s:\n",
    "            return []\n",
    "        return get(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def partition(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx >= lens:\n",
    "                return [[]]\n",
    "            cur = []\n",
    "            for i in range(idx, lens):\n",
    "                if is_para(idx, i):\n",
    "                    cur += [[s[idx: i + 1]] + x for x in dfs(i + 1)]\n",
    "            return cur\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def is_para(i, j):\n",
    "            return True if i >= j else s[i] == s[j] and is_para(i + 1, j - 1)\n",
    "\n",
    "        lens = len(s)\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isPNum(self,s):\n",
    "        l = len(s)\n",
    "        if l == 1:\n",
    "            return True\n",
    "        left = 0\n",
    "        right = l-1\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        isPNum = {}\n",
    "        cache = {}\n",
    "        def dfs(targetStr):\n",
    "            l = len(targetStr)\n",
    "            if l == 0:\n",
    "                return [[]]\n",
    "            elif l == 1:\n",
    "                return [[targetStr]]\n",
    "            if targetStr in cache:\n",
    "                return cache[targetStr]\n",
    "            res = []\n",
    "            for i in range(1,l+1):\n",
    "                temp = targetStr[:i]\n",
    "                flag = False\n",
    "                if temp in isPNum:\n",
    "                    flag = isPNum[temp]\n",
    "                else:\n",
    "                    flag = self.isPNum(temp)\n",
    "                    isPNum[temp] = flag\n",
    "                if not flag:\n",
    "                    continue\n",
    "                rest = dfs(targetStr[i:])\n",
    "                for one in rest:\n",
    "                    res.append([temp] + one)\n",
    "            \n",
    "            cache[targetStr] = res\n",
    "            return res\n",
    "        return dfs(s)\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.lru_cache(10000) \n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        result = []\n",
    "        for i in range(len(s)):\n",
    "            first = s[:i+1]\n",
    "            #print(first, s[i+1:])\n",
    "            if self.judge(first):\n",
    "                if i == len(s) - 1:\n",
    "                    result.append([first])\n",
    "                else:\n",
    "                    for res in self.partition(s[i+1:]):\n",
    "                        result.append([first] + res[:])\n",
    "        \n",
    "        return result\n",
    "                \n",
    "    @functools.lru_cache(10000)    \n",
    "    def judge(self, s):\n",
    "        for i in range(len(s) // 2):\n",
    "            if s[i] != s[len(s)-1-i]:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def isSym(self, s):\n",
    "        return s == s[::-1]\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        size = len(s)\n",
    "        if size == 0: return [[]]\n",
    "        if size == 1: return [[s]]\n",
    "\n",
    "        res = []\n",
    "        for i in range(1, size+1):\n",
    "            if self.isSym(s[:i]):\n",
    "                sub_res = self.partition(s[i:])\n",
    "                for sub_r in sub_res:\n",
    "                    res.append([s[:i]] + sub_r)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        rst = []\n",
    "        buildpartition(s, 0, len(s)-1, [], rst)\n",
    "        return rst\n",
    "    \n",
    "def buildpartition(s, l, r, tmp, rst):\n",
    "    if l > r:\n",
    "        rst.append(tmp[:])\n",
    "        return\n",
    "\n",
    "    if check(s[l:r+1]):\n",
    "        tmp.append(s[l:r+1])\n",
    "        buildpartition(s, r + 1, len(s) - 1, tmp, rst)\n",
    "        tmp.pop()\n",
    "\n",
    "    if r > l:\n",
    "        r -= 1\n",
    "        buildpartition(s, l, r, tmp, rst)\n",
    "        \n",
    "def check(s):\n",
    "    n = len(s)\n",
    "    if n < 2:\n",
    "        return True\n",
    "\n",
    "    l = 0\n",
    "    r = n - 1\n",
    "    while l <= r:\n",
    "        if s[l] != s[r]:\n",
    "            return False\n",
    "        l += 1\n",
    "        r -= 1\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if not s:\n",
    "            return []\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [[s]]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        # 判断字符串是不是回文子串\n",
    "        def is_paladrome(string):\n",
    "            length = len(string)\n",
    "            if length == 1:\n",
    "                return True\n",
    "\n",
    "            left = (length - 1) // 2\n",
    "            right = left + (length + 1) % 2\n",
    "            while 0 <= left and right <= length - 1:\n",
    "                if string[left] != string[right]:\n",
    "                    return False\n",
    "                left -= 1\n",
    "                right += 1\n",
    "            return True\n",
    "\n",
    "        # 可以提前用动态规划处理原始字符串，这样的话可以在O(1)的时间复杂度内判断一个子串是否为回文子串\n",
    "        dp = [[False for _ in range(n)] for _ in range(n)]\n",
    "        for right in range(n):\n",
    "            # left可以等于right，表示字符串长度为1个字符\n",
    "            for left in range(right + 1):\n",
    "                if s[left] == s[right] and (right - left <= 2 or dp[left + 1][right - 1]):\n",
    "                    dp[left][right] = True\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            first = s[0:i]\n",
    "            if dp[0][i - 1]:\n",
    "                if i == n:\n",
    "                    res.append([first])\n",
    "                else:\n",
    "                    second = s[i:]\n",
    "                    for r in self.partition(second):\n",
    "                        res.append([first] + r)\n",
    "\n",
    "        # for j in range(1, n + 1):\n",
    "        #     first = s[0:j]\n",
    "        #     if is_paladrome(first):\n",
    "        #         if j == n:\n",
    "        #             res.append([first])\n",
    "        #         else:\n",
    "        #             second = s[j:]\n",
    "        #             for r in self.partition(second):\n",
    "        #                 res.append([first] + r)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.error = 0\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if not s:\n",
    "            self.error = 1\n",
    "            return []\n",
    "        l = len(s)\n",
    "        if l == 1:\n",
    "            return [[s]]\n",
    "        res = []\n",
    "        dp = [[0 for i in range(l)] for j in range(l)]\n",
    "        for i in range(l):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(l-1,-1,-1):\n",
    "            for j in range(i+1, l):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == j-1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "        for i in range(l):\n",
    "            if dp[0][i]:\n",
    "                for item in self.partition(s[i+1:]):\n",
    "                    res.append([s[:i+1]]+item)\n",
    "                if i > l-2:\n",
    "                    res.append([s[:i+1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    all_path = []\n",
    "    path = []\n",
    "\n",
    "    def backtrace(self, s, start):\n",
    "        if start >= len(s):\n",
    "            self.all_path.append(self.path.copy())\n",
    "            return\n",
    "        \n",
    "        for i in range(start, len(s)+1):\n",
    "            sub_s = s[start:i]\n",
    "            print(start, i, s, sub_s)\n",
    "            if not sub_s:\n",
    "                continue\n",
    "            if sub_s == sub_s[::-1]:\n",
    "                self.path.append(sub_s)\n",
    "                self.backtrace(s, i)\n",
    "                self.path.pop()\n",
    "            \n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.all_path.clear()\n",
    "        self.backtrace(s, 0)\n",
    "        return self.all_path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    all_path = []\n",
    "    path = []\n",
    "\n",
    "    def backtrace(self, s, start):\n",
    "        if start >= len(s):\n",
    "            self.all_path.append(self.path.copy())\n",
    "            return\n",
    "        \n",
    "        for i in range(start, len(s)+1):\n",
    "            sub_s = s[start:i]\n",
    "            # print(start, i, s, sub_s)\n",
    "            if not sub_s:\n",
    "                continue\n",
    "            if sub_s == sub_s[::-1]:\n",
    "                self.path.append(sub_s)\n",
    "                self.backtrace(s, i)\n",
    "                self.path.pop()\n",
    "            \n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.all_path.clear()\n",
    "        self.backtrace(s, 0)\n",
    "        return self.all_path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "    def huiWen(self, c):\n",
    "        for i in range(int(len(c) / 2)):\n",
    "            if c[i] != c[len(c) -i-1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def generatePartition(self, s, start, cur):\n",
    "        if start == len(s):\n",
    "            print(cur)\n",
    "            self.res.append(cur.copy())\n",
    "            return\n",
    "        for i in range(start, len(s)):\n",
    "            tmp = s[start:i+1]\n",
    "            print(tmp)\n",
    "            if self.huiWen(tmp):\n",
    "                cur.append(tmp)\n",
    "                self.generatePartition(s, i+1, cur)\n",
    "                cur.pop()\n",
    "    \n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.res.clear()\n",
    "        cur = []\n",
    "        self.generatePartition(s, 0, cur)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    path = []\n",
    "    result = []\n",
    "    \n",
    "    def isParli(self, s):\n",
    "        return s == s[::-1]\n",
    "\n",
    "    def backtracking(self, s, start_idx):\n",
    "        if start_idx >= len(s):\n",
    "            self.result.append(self.path.copy())\n",
    "        for i in range(start_idx, len(s)):\n",
    "            cur_s = s[start_idx:i+1]\n",
    "            if self.isParli(cur_s):\n",
    "                self.path.append(cur_s)\n",
    "                self.backtracking(s, i + 1)\n",
    "                self.path.pop()\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.path.clear()\n",
    "        self.result.clear()\n",
    "        self.backtracking(s, 0)\n",
    "        return self.result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    path = []\n",
    "    result = []\n",
    "\n",
    "    def is_pardo(self, s):\n",
    "        return s == s[::-1]\n",
    "\n",
    "    def backtrack(self, s, start_idx):\n",
    "        if len(s) == start_idx:\n",
    "           self.result.append(self.path.copy())\n",
    "\n",
    "        for i in range(start_idx, len(s)):\n",
    "            cur = s[start_idx:i+1]\n",
    "            if self.is_pardo(cur):\n",
    "                self.path.append(cur)\n",
    "                self.backtrack(s, i+1)\n",
    "                self.path.pop()\n",
    "            else:\n",
    "                continue\n",
    "          \n",
    "\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.path.clear()\n",
    "        self.result.clear()\n",
    "        self.backtrack(s, 0)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.res.clear()\n",
    "        if not s:\n",
    "            return self.res\n",
    "        record = []\n",
    "        self.dfs(s, 0, record)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, s, index, record):\n",
    "        if index >= len(s):\n",
    "            #print(record)\n",
    "            self.res.append(record[:])\n",
    "            return\n",
    "        for i in range(index, len(s)):\n",
    "            if self.isPalindrome(s, index, i):\n",
    "                record.append(s[index:i+1])\n",
    "                #print(record)\n",
    "                self.dfs(s, i+1, record)\n",
    "                record.pop()\n",
    "        return\n",
    "    def isPalindrome(self, s, l, r):\n",
    "        if l > r:\n",
    "            return True\n",
    "        if s[l] == s[r]:\n",
    "            return self.isPalindrome(s, l+1, r-1)\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "    path = []\n",
    "    def backtrack(self, s: str, start_index: int):\n",
    "        if start_index >= len(s):\n",
    "            self.res.append(self.path[:])\n",
    "            return\n",
    "        for i in range(start_index, len(s)):\n",
    "            if self.ispalindrome(s, start_index, i):\n",
    "                self.path.append(s[start_index: i+1])\n",
    "                self.backtrack(s, i + 1)\n",
    "                self.path.pop()\n",
    "\n",
    "    def ispalindrome(self, s: str, start: int, end: int):\n",
    "        i, j = start, end\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.res.clear()\n",
    "        self.path.clear()\n",
    "        self.backtrack(s, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        data = {}\n",
    "        for i in range(len(s)):\n",
    "            data[i] = [(i, s[i])]\n",
    "            for j in range(i + 1, len(s)):\n",
    "                start = i\n",
    "                stop = j\n",
    "                while start < stop:\n",
    "                    if s[start] == s[stop]:\n",
    "                        start += 1\n",
    "                        stop -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    data[i].append((j, s[i:j+1]))\n",
    "\n",
    "        res = []\n",
    "        stack = [[i] for i in data[0]]\n",
    "        while len(stack):\n",
    "            e = stack.pop()\n",
    "            if e[-1][0] == len(s) - 1:\n",
    "                res.append([i[1] for i in e])\n",
    "            else:\n",
    "                for i in data[e[-1][0] + 1]:\n",
    "                    bak = e.copy()\n",
    "                    bak.append(i)\n",
    "                    stack.append(bak)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s):\n",
    "            \"\"\"\n",
    "            :type s: str\n",
    "            :rtype: List[List[str]]\n",
    "            \"\"\"\n",
    "            r = []\n",
    "            stop = {} # string(char) to position\n",
    "            p = {}\n",
    "            mul = []\n",
    "            sl = len(s)\n",
    "            for i in range(sl):\n",
    "                stop[s[i]] = stop[s[i]] + [i] if s[i] in stop else [i]\n",
    "            for i in stop:\n",
    "                for c in range(len(stop[i])):\n",
    "                    cc = stop[i][c]\n",
    "                    for ci in range(c, len(stop[i])):\n",
    "                        cci = stop[i][ci]+1\n",
    "                        si = s[cc: cci]\n",
    "                        if self.ispalin(si):\n",
    "                            p[cc] = p[cc] + [(cci, si)] if cc in p else [(cci, si)]\n",
    "                    l = len(p[cc])\n",
    "                    if l > 1:\n",
    "                        mul += [(cc, l-1)]\n",
    "            if len(mul) == 0:\n",
    "                return [list(s)]\n",
    "            mul.sort()\n",
    "            mulinp = {}\n",
    "            for i in range(len(mul)):\n",
    "                mulinp[mul[i][0]] = i\n",
    "            sl -= 1\n",
    "            pre = []\n",
    "            pp = 0\n",
    "            path = [-1 for i in mul]\n",
    "            pind = -1\n",
    "            paths = [[]]\n",
    "            while path[0] < mul[0][1] or path[pind] < mul[pind][1]:\n",
    "                while pp <= sl:\n",
    "                    if pp not in mulinp:\n",
    "                        pre += [p[pp][0][1]]\n",
    "                        paths[-1] += [p[pp][0][1]]\n",
    "                        pp += 1\n",
    "                    else:\n",
    "                        pind = mulinp[pp]\n",
    "                        path[pind] += 1\n",
    "                        pre += [p[pp][path[pind]][1]]\n",
    "                        paths += [paths[-1].copy()+[p[pp][path[pind]][1]]]\n",
    "                        pp = p[pp][path[pind]][0]\n",
    "                r += [pre]\n",
    "                pp = mul[pind][0]\n",
    "                paths.pop()\n",
    "                pre = paths[-1].copy()\n",
    "                while pind > 0 and path[pind] == mul[pind][1]:\n",
    "                    path[pind] = -1\n",
    "                    for i in range(len(path)):\n",
    "                        if path[-1-i] != -1:\n",
    "                            pind = len(path)-i-1\n",
    "                            break\n",
    "                    pp = mul[pind][0]\n",
    "                    paths.pop()\n",
    "                    pre = paths[-1].copy()\n",
    "            return r\n",
    "\n",
    "    def ispalin(self, s):\n",
    "        i = 0\n",
    "        l = len(s)/2-1\n",
    "        while i <= l:\n",
    "            if s[i] != s[-i-1]:\n",
    "                return False\n",
    "            i += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def is_re(word):\n",
    "            word_len = len(word)\n",
    "            if word ==1:\n",
    "                return True\n",
    "            left = 0\n",
    "            right = word_len-1\n",
    "            while left<=right:\n",
    "                if word[left] != word[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "         \n",
    "        s_len = len(s)\n",
    "\n",
    "        s_list = [[s[i]] for i in range(s_len)]\n",
    "        for i in range(s_len-1,-1,-1):\n",
    "            for j in range(i-1,  -1,-1):\n",
    "                w = s[j:i+1]\n",
    "                if is_re(w):\n",
    "                    s_list[i].append(w)\n",
    "        # print(s_list)\n",
    "        def dfs(i):\n",
    "            if i<0:\n",
    "                return \n",
    "            cur = []\n",
    "            for w in s_list[i]:\n",
    "                word = dfs(i-len(w))\n",
    "                if word:\n",
    "                    for v in word:\n",
    "                        v.append(w)\n",
    "                        cur.append(v)\n",
    "                else:\n",
    "                    cur.append([w])\n",
    "            return cur\n",
    "        return dfs(s_len-1)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def is_re(word):\n",
    "            word_len = len(word)\n",
    "            if word ==1:\n",
    "                return True\n",
    "            left = 0\n",
    "            right = word_len-1\n",
    "            while left<=right:\n",
    "                if word[left] != word[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "         \n",
    "        s_len = len(s)\n",
    "\n",
    "        s_list = [[s[i]] for i in range(s_len)]\n",
    "        for i in range(s_len):\n",
    "            for j in range(i+2, s_len+1):\n",
    "                w = s[i:j]\n",
    "                if is_re(w):\n",
    "                    s_list[i].append(w)\n",
    "        # print(s_list)\n",
    "        def dfs(i):\n",
    "            if i>=s_len:\n",
    "                return []\n",
    "            cur = []\n",
    "            for w in s_list[i]:\n",
    "                word = dfs(i+len(w))\n",
    "                if word:\n",
    "                    for v in word:\n",
    "                        cur.append([w]+v)\n",
    "                else:\n",
    "                    cur.append([w])\n",
    "            return cur\n",
    "        return dfs(0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res = []\n",
    "        self.backtracking(s, 0, [], res)\n",
    "        return res\n",
    "\n",
    "    def backtracking(self, s, start, data, res):\n",
    "        if start > len(s):\n",
    "            return\n",
    "\n",
    "        if start == len(s):\n",
    "            res.append(data[:])\n",
    "            return\n",
    "\n",
    "        for i in range(start, len(s)):\n",
    "            cur = s[start: i + 1]\n",
    "            if self.is_para(cur):\n",
    "                data.append(cur)\n",
    "                self.backtracking(s, i + 1, data, res)\n",
    "                data.pop()\n",
    "\n",
    "\n",
    "    def is_para(self, input):\n",
    "        left, right = 0, len(input) - 1\n",
    "\n",
    "        while left < right and right > 0 and left < len(input):\n",
    "            if input[left] != input[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res = []\n",
    "        def par(s):\n",
    "            return s==s[::-1]\n",
    "\n",
    "        def backtrack(path, res,s):\n",
    "            if not s:\n",
    "                res.append(copy.deepcopy(path))\n",
    "            for i in range(len(s)):\n",
    "                if par(s[:i+1]):\n",
    "                    path.append(s[:i+1])\n",
    "                    backtrack(path, res, s[i+1:])\n",
    "                    path.pop()\n",
    "            return res\n",
    "\n",
    "\n",
    "        res = backtrack([], [], s)\n",
    "        return res  ## 这种所有的方案就要用backtrack方法来解决\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        # res = []\n",
    "        # path = []\n",
    "        # def backtrack(s, startIndex):\n",
    "        #     if startIndex >= len(s):\n",
    "        #         return res.append(path[:])\n",
    "        #     for i in range(startIndex, len(s)):\n",
    "        #         p = s[startIndex:i+1]\n",
    "        #         if p == p[::-1]:\n",
    "        #             path.append(p)\n",
    "        #         else:\n",
    "        #             continue\n",
    "        #         backtrack(s, i+1)\n",
    "        #         path.pop()\n",
    "        # backtrack(s, 0)\n",
    "        # return res\n",
    "\n",
    "\n",
    "        l=len(s)\n",
    "        dp=[[] for _ in range(l+1)]\n",
    "        dp[0]=[[]]\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(i):\n",
    "                tmp=s[j:i]\n",
    "                if tmp==tmp[::-1]:\n",
    "                    dp[i] += [x+[tmp] for x in dp[j]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        # res = []\n",
    "        # path = []\n",
    "        # def backtrack(s, startIndex):\n",
    "        #     if startIndex >= len(s):\n",
    "        #         return res.append(path[:])\n",
    "        #     for i in range(startIndex, len(s)):\n",
    "        #         p = s[startIndex:i+1]\n",
    "        #         if p == p[::-1]:\n",
    "        #             path.append(p)\n",
    "        #         else:\n",
    "        #             continue\n",
    "        #         backtrack(s, i+1)\n",
    "        #         path.pop()\n",
    "        # backtrack(s, 0)\n",
    "        # return res\n",
    "\n",
    "\n",
    "        l=len(s)\n",
    "        dp=[[] for _ in range(l+1)]\n",
    "        dp[0]=[[]]\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(i):\n",
    "                tmp=s[j:i]\n",
    "                if tmp==tmp[::-1]:\n",
    "                    dp[i] += [x+[tmp] for x in dp[j]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        substr_list = []\n",
    "\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                if substr_list:\n",
    "                    ans.append(list(substr_list))\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if s[i:j + 1] == s[i:j + 1][::-1]:\n",
    "                    substr_list.append(s[i:j + 1])\n",
    "                    dfs(j + 1)\n",
    "                    substr_list.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        state = []\n",
    "        n = len(s)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(state[:])\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                if s[i:j+1] == s[i:j+1][::-1]:\n",
    "                    state.append(s[i:j+1])\n",
    "                    dfs(j+1)\n",
    "                    state.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        dp = [[False] * len(s) for _ in range(len(s))]\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            for j in range(i, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j - i <= 1:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i + 1][j - 1]:\n",
    "                        dp[i][j] = True\n",
    "        result = []\n",
    "        path = []\n",
    "        def backtracking(start):\n",
    "            if start == len(s):\n",
    "                result.append(path[:])\n",
    "                return\n",
    "            for i in range(start, len(s)):\n",
    "                if dp[start][i]:\n",
    "                    path.append(s[start:i + 1])\n",
    "                    backtracking(i + 1)\n",
    "                    path.pop()\n",
    "        backtracking(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(i, start):\n",
    "            if i == n:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "\n",
    "            if i < n - 1:\n",
    "                dfs(i + 1, start)\n",
    "            \n",
    "            t = s[start: i + 1]\n",
    "            if t == t[::-1]:\n",
    "                path.append(t)\n",
    "                dfs(i+1, i+1)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
